package com.lw.leetcode.tree.c;

import com.lw.leetcode.tree.TreeNode;

import java.util.*;

/**
 * 987. 二叉树的垂序遍历
 *
 * @Author liw
 * @Date 2021/7/31 14:04
 * @Version 1.0
 */
public class VerticalTraversal {

    public static void main(String[] args) {
        VerticalTraversal test = new VerticalTraversal();
        TreeNode instance = TreeNode.getInstance10();
        List<List<Integer>> lists = test.verticalTraversal(instance);
        System.out.println(lists);
    }

    public List<List<Integer>> verticalTraversal(TreeNode root) {
        Map<Integer, Map<Integer, PriorityQueue<Integer>>> map = new HashMap<>();
        find(root, map, 0, 0);
        Set<Integer> set = map.keySet();
        int min = 0;
        int max = 0;
        for (Integer value : set) {
            min = Math.min(min, value);
            max = Math.max(max, value);
        }
        System.out.println(map);
        List<List<Integer>> all = new ArrayList<>(map.size());
        for (int i = min; i <= max; i++) {
            Map<Integer, PriorityQueue<Integer>> itemMap = map.get(i);
            List<Integer> list = new ArrayList<>();
            for (Map.Entry<Integer, PriorityQueue<Integer>> entry : itemMap.entrySet()) {
                PriorityQueue<Integer> value = entry.getValue();
                while (!value.isEmpty()) {
                    list.add(value.poll());
                }
            }
            all.add(list);
        }
        return all;
    }

    private void find(TreeNode node, Map<Integer, Map<Integer, PriorityQueue<Integer>>> map, int index, int d) {
        if (node == null) {
            return;
        }
        PriorityQueue<Integer> list = map.computeIfAbsent(index, v -> new TreeMap<>()).computeIfAbsent(d, v -> new PriorityQueue<>());
        list.add(node.val);
        find(node.left, map, index - 1, d + 1);
        find(node.right, map, index + 1, d + 1);
    }
}
